class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        def func(s):
            while len(s) != 0:
                found = False
                for word in wordDict:
                    if s.startswith(word):
                        s = s[len(word):]
                        found = True
                if not found:
                    return False
            return True

        return func(s)

print(Solution().wordBreak("cars", ["car","ca","rs"]))
